package leetcode;

//线段树
public class SegmentTree {

	private int N = 10;
	private int[] tree = new int[N * 4];

	private int[] nums = new int[N];
	//建造线段树，num 是下标，left和right表示的是这个区间的左右端点
	public void build(int num, int left, int right) {
		if(left == right){ 
			//等于输入的数组中的left的值
			tree[num] = nums[left];
	        return;  
	    }  
		//内存占用大约为4倍的点数，所以建数组的时候为4 * N
		int mid = (left + right) / 2;
		build(num * 2, left, mid);
		build(num * 2 + 1, mid + 1, right);
		//这个根据具体情况具体写，题目上是求和，所以这里是加
		//如果变成最大值，那么这儿应该相应的改成最大值
		tree[num] = tree[num * 2] + tree[num * 2 + 1];
	}
	
	//继承了上面的num，le，ri，保证了一致性，同时此处做的是对于第x个点增加y的操作
	public void update(int num, int left, int right, int x, int y) {
		if (left == right) {
			tree[num] += y;
			return;
		}
		int mid = (left + right) / 2;
		//寻找到x所对应的tree[num]
		if (x <= mid){
			update(num * 2 + 1, left, mid, x, y);
		}else{
			update(num * 2 + 2, mid + 1, right, x, y);
		}
		tree[num] = tree[num * 2 + 1] + tree[num * 2 + 2];
	}
	
	//查询,查询x ... y的总和
	public int query(int num, int left, int right, int x, int y) {
		//此时tree[num]就已经是这一部分的有效数据了，所以直接return即可
		if (x <= left && y >= right) {
			return tree[num];
		}
		int mid = (left + right) / 2;
		int ans = 0;
		if (x <= mid)
			ans += query(num * 2 + 1, left, mid, x, y);
		if (y > mid)
			ans += query(num * 2 + 2, mid + 1, right, x, y);
		return ans;
	}
}
